이중 연결 리스트

이중doubly 링크드 리스트는
한 노드가 자기 앞에 있는 노드를 가리키는 포인터도 가지고 있는 경우를 말한다.

(노드1) <-> (노드2) <-> (노드3) 이렇게

여기서는 맨 앞의 노드를 헤드라고 부른다고.

삽입

1. 맨 앞에 삽입

   1. 새 노드를 만들고
   2. 기존의 헤드의 prev 포인터가 새 노드를 향하게 만든다.
   3. 새 노드의 Next 를 기존의 헤드 노드로
   4. 새 노드의 prev 포인터를 null 로 한다.

2. 맨 끝에 삽입

   1. 새 노드를 만들고
   2. 기존의 마지막 노드의 next가 새 노드를 가리키고
   3. 새 노드의 prev가 기존의 마지막 노드로
   4. 새 노드의 Next를 Null로

3. 중간에 삽입

   1. 새 노드를 만들고
   2. 새 노드의 prev와 next를 각각 지정해주고
   3. 앞 노드의 next와 뒤 노드의 prev를 새 노드로

삭제

삭제도 단일 연결 리스트와 마찬가지로 free()를 통해 메모리를 비워줘야 하는것을 신경써야 한다.

1. 맨 앞 노드 삭제
2. 맨 끝 노드 삭제
3. 중간 노드 삭제

정리

순서가 중요한 데이터들을 모아두는 자료형을 '리스트'라고 하고
가장 간단한건 '배열'이다.
하지만 미리 크기를 지정해야된다는 단점과 안에 요소를 삽입하거나 삭제할때 불편하다는 단점 때문에 '링크드 리스트'라는 자료형을 사용한다.

포인터

링크드 리스트에서 사용되는 '포인터'라는게 등장.
메모리의 주소값을 가리키고있는 변수다.
링크드 리스트는 배열처럼 요소들이 서로 이웃하고 있지 않기 때문에,
리스트에 요소를 넣을 때, 항상 새로운 노드를 만들고 그 노드의 주소값을 이전 노드에 저장한다.
그래서 리스트를 처음부터 끝까지 순회할 때 각 노드에 적힌 주소값들을 타고 타고 이동하는것.

링크드 리스트에 삽입, 삭제

삽입하거나 삭제할 때 신경써야하는 부분이 있다.
새로운 노드를 넣을 때 1) 먼저 새로운 노드를 만들고 새 노드의 포인터에 다음 노드의 주소값을 넣어주고, 2) 그 다음에 새 노드의 주소값을 이전 노드의 포인터에 넣어줘야 한다.
그러지 않고 먼저 새 노드의 주소값을 앞 노드의 포인터에 넣어버리면, 기존에 가지고 있던 주소값이 사라지게 되고 새 노드가 자신의 포인터에 넣을 주소값을 알 수 없게 된다.
삭제할 때에도 마찬가지로 free()함수로 해당 메모리를 비워줘야 하기 때문에 (가비지 컬레거가 없기 때문에) 주소값을 가지고 있어야 한다.
(이런 과정들을 직접 구현해야 하기 때문에 C언어가 공부해볼만 한 언어라고 한다.)

스택

데이터를 저장하기 위해 사용되는 간단한 데이터 구조.
먼저 들어온게 나중에 나간다.
근데 왜 굳이 그렇게 해야될까? 넣는 순서에 상관 없이 아무렇게나 접근하고 읽고 쓰고 할 수 있으면 더 좋은거 아닌가?
굳이 마지막으로 넣은 자료에만 접근 가능하도록 강력히 제한을 둔 스택 자료구조를 사용하는 이유는 바로 에러를 막기 위해서.

스택을 사용하면 편한 경우?

• 괄호 짝 맞추기
• 인픽스를 포스트픽스로 변환하기
  (1+2)*3 처럼 인간에게 익숙한 방식은 '인픽스'.
  컴퓨터는 '포스트픽스'(혹은 프리픽스) 방식을 선호한다.
  위의 식을 포스트 픽스로는 312+*.
  해석하면 연산자의 왼쪽 두 숫자를 사용해 연산을 하고 그 결과를 다시 왼쪽 숫자와 함께 오른쪽 연산자에 해당하는 연산을 실행.
• 포스트 픽스 수식 계산하기
• 함수 호출 구현하기
• 스팬(span) 찾기
• 웹 브라우저에서 방문한 페이지 기록 관리하기
• 텍스트 에디터에서 작업 취소 과정
• html와 xml에서 태그 짝 맞추기

정의

삽입과 삭제가 한쪽 끝에서 이루어지는, 순서가 매겨진 리스트.
이 끝을 탑(Top)이라고 부른다.
('리스트'의 종류이니까 순서가 중요하다는 것을 알 수 있다. 그리고 스택에서 중요한 순서는 바로 삽입된 순서라는것도 알 수 있다.)

스택 ADT

ADT는 '추상데이터타입'.
실제로 어떻게 구현되었든 상관 없이 특정 방식으로 작동 한다면 그것을 '스택'이라고 부를 수 있다는 것이다.
그러니까 그 '특정 방식'을 잘 이해하는것이 중요.
push() pop()이 일단 가장 중요한 연산들.